{\magonebf 4.3 Dictionaries (dictionary)}

\decltwo dictionary K I

{\bf 1. Definition}

An instance $D$ of the parameterized data type \name\ is a collection
of items ($dic\_item$). Every item in $D$ contains a key from the linearly 
ordered data type $K$, called the key type of $D$, and an information from the 
data type $I$, called the information type  of $D$. The number of items in $D$ 
is called the size of $D$. A dictionary of size zero is called the empty 
dictionary. We use $<k,i>$ to denote an item with key $k$ and information 
$i$ ($i$ is said to be the information associated with key $k$).  For each 
$k \in K$ there is at most one $i \in I$ with $<k,i> \in D$.


\bigskip
{\bf 2. Creation}

a) \create D {}

b) $\_dictionary${\tt <}$K,I,dic\_impl${\tt >} $D$ ;

creates an instance \var\ of type \name\ and initializes it with the
empty dictionary. Variant a) chooses the default data structure
(cf.~4.3.4), and variant b) chooses class $dic\_impl$ as the 
implementation of the dictionary (cf.~section~9 for a list of possible
implementation parameters).


\bigskip
{\bf 3. Operations}

\+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
\+\op K         key {dic\_item\ it}  
                              {returns the key of item $it$.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op I         inf {dic\_item\ it}  
                              {returns the information of item $it$.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op dic\_item insert {K\ k,\ I\ i} 
                              {associates the information $i$ with the key $k$.}
\+\nop                        {If there is an item $<k,j>$ in \var\ then $j$ is}
\+\nop                        {replaced by i, else a new item $<k,i>$ is added}
\+\nop                        {to \var. In both cases the item is returned.}
\smallskip
\+\op dic\_item lookup {K\ k} 
                              {returns the item with key $k$ (nil if no such }
\+\nop                        {item exists in \var).}
\smallskip
\+\op I         access {K\ k} 
                              {returns the information associated with key $k$}
\+\nop                        {\precond there is an item with key $k$ in \var.}
\smallskip
\+\op void      del {K\ k}         
                              {deletes the item with key $k$ from \var}
\+\nop                        {(null operation, if no such item exists).}
\smallskip
\+\op void      del\_item {dic\_item\ it}   
                              {removes item $it$ from \var.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op void      change\_inf {dic\_item\ it,\ I\ i} 
                              {makes $i$ the information of item $it$.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op void      clear {}      
                              {makes \var\ the empty dictionary.}
\smallskip 
\+\op bool      empty {}      
                              {returns true if \var\ is empty, false otherwise.}
\smallskip 
\+\op int       size {}       
                              {returns the size of \var.}




\bigskip
{\bf 4. Implementation}


Dictionaries are implemented by randomized search trees ([AS89]). Operations 
insert, lookup, del\_item, del take time $O(\log n)$, key, inf, empty, size,
change\_inf take time $O(1)$, and clear takes time $O(n)$. Here $n$ is the 
current size of the dictionary. The space requirement is $O(n)$.
 


\bigskip
{\bf 5. Example}
\smallskip
\input prog/dic.prog

